#include <cstring>
class Solution {
public:
    int LIS(vector<int>& arr) {
       int len = arr.size();
       //dp[i]代表以i位置为结尾的子序列中最长上升子序列的长度
       if(len == 0)
       {
            return 0;
       }
       int dp[len];
       memset(dp,0,sizeof(dp));
       int ret = 0;
       for(int i = 0;i<len;i++)
       {
            for(int j = 0;j<i;j++)
            {
                if(arr[i]>arr[j])
                {
                    dp[i] = max(dp[i],dp[j]+1);
                }
                ret = max(ret,dp[i]);
            }
       }
       return ret+1;
    }
};